package backMind

// 正则表达式匹配问题--回溯思想

type RegexExpress struct {
	matched bool
	pattern []byte // 正则表达式
	pLen    int    // 正则表达式长度
}

func NewRegexExpress(pattern []byte, pLen int) *RegexExpress {
	return &RegexExpress{
		pattern: pattern,
		pLen:    pLen,
	}
}

func (regex *RegexExpress) Match(text []byte, tLen int) bool {
	regex.matched = false
	regex.rMatch(0, 0, text, tLen)
	return regex.matched
}

// ti表示文本串当前位置，pj表示模式串当前位置
func (regex *RegexExpress) rMatch(ti, pj int, text []byte, tLen int) {
	// 如果已经匹配则结束
	if regex.matched {
		return
	}
	// 正则表达式结尾了
	if pj == regex.pLen {
		// 文本串也到结尾了
		if ti == tLen {
			regex.matched = true
		}
		return
	}
	// 匹配任意个字符(至少一个)
	if regex.pattern[pj] == '*' {
		// 继续匹配文本串剩余字符
		for k := 0; k <= tLen-ti; k++ {
			regex.rMatch(ti+k, pj+1, text, tLen)
		}
	} else if regex.pattern[pj] == '?' { // ?匹配0个或1个字符
		regex.rMatch(ti, pj+1, text, tLen)
		regex.rMatch(ti+1, pj+1, text, tLen)
	} else if ti < tLen && regex.pattern[pj] == text[ti] { // 纯字符才能匹配
		regex.rMatch(ti+1, pj+1, text, tLen)
	}
}
